home *** CD-ROM | disk | FTP | other *** search
/ Chip: Internet / Chip Internet.iso / viewer / gsnt / source / slzwd.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-12  |  7.3 KB  |  239 lines
  1. /* Copyright (C) 1991, 1992, 1993 Aladdin Enterprises.  All rights reserved.
  2.  
  3. This file is part of Ghostscript.
  4.  
  5. Ghostscript is distributed in the hope that it will be useful, but
  6. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  7. to anyone for the consequences of using it or for whether it serves any
  8. particular purpose or works at all, unless he says so in writing.  Refer
  9. to the Ghostscript General Public License for full details.
  10.  
  11. Everyone is granted permission to copy, modify and redistribute
  12. Ghostscript, but only under the conditions described in the Ghostscript
  13. General Public License.  A copy of this license is supposed to have been
  14. given to you along with Ghostscript so you can know your rights and
  15. responsibilities.  It should be in a file named COPYING.  Among other
  16. things, the copyright notice and this notice must be preserved on all
  17. copies.  */
  18.  
  19. /* slzwd.c */
  20. /* LZW decoding filter */
  21. #include "stdio_.h"    /* includes std.h */
  22. #include "gdebug.h"
  23. #include "stream.h"
  24.  
  25. /********************************************************/
  26. /* LZW routines are based on:                */
  27. /* Dr. Dobbs Journal --- Oct. 1989.             */
  28. /* Article on LZW Data Compression by Mark R. Nelson     */
  29. /********************************************************/
  30.  
  31. /*
  32.  * This code implements enhancements to the LZW algorithm.
  33.  * For a full explanation of the algorithm, see the file slzwe.c.
  34.  */
  35.  
  36. /* Define the special codes */
  37. #define code_reset 256
  38. #define code_eod 257
  39. #define code_0 258            /* first assignable code */
  40.  
  41. /* ------ LZWDecode filter ------ */
  42.  
  43. typedef struct lzw_decode_s {
  44.     byte datum;
  45.     byte len;            /* length of code */
  46.     ushort prefix;            /* code to be prefixed */
  47. } lzw_decode;
  48. #define lzw_decode_max 4096        /* must be 4096 */
  49.  
  50. typedef struct lzw_decode_table_s {
  51.     lzw_decode decode[lzw_decode_max+1];
  52. } lzw_decode_table;
  53.  
  54. /* Export the size of the LZW decoding table. */
  55. const uint s_LZWD_table_sizeof = sizeof(lzw_decode_table);
  56.  
  57. /* Initialize LZWDecode filter */
  58. void
  59. s_LZWD_init(register stream *s, lzw_decode_table *table, int enhanced)
  60. {    register lzw_decode *dc;
  61.     register int i;
  62.     s->bits_left = 0;
  63.     s->state.lzw.next_code = code_0;
  64.     s->state.lzw.code_size = 9;
  65.     s->state.lzw.prev_code = -1;
  66.     s->odd = -1;
  67.     s->state.lzw.enhanced = enhanced;
  68.     s->state.lzw.decode_table = table;
  69.     dc = table->decode;
  70.     dc[code_reset].len = 255;
  71.     dc[code_eod].len = 255;
  72.     for ( i = 0; i < 256; i++, dc++ )
  73.       dc->datum = i, dc->len = 1, dc->prefix = code_eod;
  74. }
  75.  
  76. /* Buffer refill for LZWDecode filter */
  77. /****** DOESN'T HANDLE CODES LONGER THAN THE BUFFER SIZE ******/
  78. private int
  79. s_LZWD_read_buf(register stream *s)
  80. {    int code = s->odd;
  81.     int prev_code = s->state.lzw.prev_code;
  82.     byte bits = s->bits;
  83.     int bits_left = s->bits_left;
  84.     int code_size = s->state.lzw.code_size;    /* cache only */
  85.     int code_mask = (1 << code_size) - 1;
  86.     int next_code = s->state.lzw.next_code;
  87.     register stream *strm = s->strm;
  88.     register byte *p = s->cbuf;
  89.     byte *limit = p + s->bsize;
  90.     lzw_decode *table = s->state.lzw.decode_table->decode;
  91.     lzw_decode *dc_next = table + next_code;
  92.     int enhanced = s->state.lzw.enhanced;
  93.     lzw_decode *dc;
  94.     uint prev_len, len;
  95.     int c;
  96.     byte *p1;
  97.     if_debug2('w', "[w]read_buf: code_size=%d next_code=%d\n",
  98.           code_size, next_code);
  99.     if ( prev_code >= 0 )
  100.         prev_len = table[prev_code].len;
  101.     if ( code >= 0 ) goto add;
  102. top:    code = bits << (code_size - bits_left);
  103.     bits = sgetc(strm);
  104.     if ( (bits_left += 8 - code_size) < 0 )
  105.        {    code += bits << -bits_left;
  106.         bits = sgetc(strm);
  107.         bits_left += 8;
  108.        }
  109.     code = (code + (bits >> bits_left)) & code_mask;
  110.     if_debug2('W', "[W]reading 0x%x,%d", code, code_size);
  111.     /* Invert the code-shortening algorithm described in slzwd.c. */
  112.     if ( enhanced )
  113.        {    uint N = code_mask + 1;
  114.         uint M = (prev_code < 0 ? next_code : next_code + 1);
  115.         uint D = N - M;
  116.         if ( code < D << 1 )    /* S-1 bits */
  117.             code >>= 1, ++bits_left;
  118.         else if ( !(code & 1) )    /* S bits, < N/2 */
  119.             code >>= 1;
  120.         else            /* S bits, >= N/2 */
  121.             code = (code >> 1) - N / 2 + M;
  122. #ifdef DEBUG
  123. if ( gs_debug['W'] )
  124.    {    if ( enhanced )
  125.         dprintf2(" -> 0x%x,%d", code,
  126.              (code < D ? code_size - 1 : code_size));
  127.    }
  128. #endif
  129.        }
  130. #ifdef DEBUG
  131. if ( gs_debug['W'] )
  132.     dputc('\n');
  133. #endif
  134. add:    /*
  135.      * There is an anomalous case where a code S is followed
  136.      * immediately by another occurrence of the S string.
  137.      * In this case, the next available code will be defined as
  138.      * S followed by the first character of S, and will be
  139.      * emitted immediately after the code S.  We have to
  140.      * recognize this case specially, by noting that the code is
  141.      * equal to next_code.
  142.      */
  143.     if ( code == next_code )
  144.        {    /* Fabricate the entry for the code.  It will be */
  145.         /* overwritten immediately, of course. */
  146.         for ( c = prev_code; c != code_eod; c = table[c].prefix )
  147.             dc_next->datum = c;
  148.         len = prev_len + 1;
  149.         dc_next->len = min(len, 255);
  150.         dc_next->prefix = prev_code;
  151.         if_debug3('w', "[w]decoding anomalous 0x%x=0x%x+%c\n",
  152.               next_code, prev_code, dc_next->datum);
  153.        }
  154.     /* See if there is enough room for the code. */
  155.     len = table[code].len;
  156.     if ( len == 255 )
  157.        {    /* Check for special code (reset or end). */
  158.         /* We set their lengths to 255 to avoid doing */
  159.         /* an extra check in the normal case. */
  160.         switch ( code )
  161.            {
  162.         case code_reset:
  163.             if_debug1('w', "[w]reset: next_code was %d\n",
  164.                   next_code);
  165.             next_code = code_0;
  166.             dc_next = table + code_0;
  167.             s->state.lzw.code_size = code_size = 9;
  168.             code_mask = (1 << 9) - 1;
  169.             prev_code = -1;
  170.             goto top;
  171.         case code_eod:
  172.             s->end_status = EOFC;
  173.             goto out;
  174.            }
  175.         /* The code length won't fit in a byte, */
  176.         /* compute it the hard way. */
  177.         for ( c = code, len = 0; c != code_eod; len++ )
  178.             c = table[c].prefix;
  179.         if_debug2('w', "[w]long code %d, length=%d\n", code, len);
  180.        }
  181.     if ( limit - p < len )
  182.        {    s->odd = code;
  183.         goto out;
  184.        }
  185.     /* Copy the string to the buffer (back to front). */
  186.     c = code;
  187.     p1 = p += len;
  188.     do
  189.        {    *--p1 = (dc = &table[c])->datum;
  190.        }
  191.     while ( (c = dc->prefix) != code_eod );
  192.     /* Add a new entry to the table */
  193.     if ( prev_code >= 0 )
  194.     {    /* Unfortunately, we have to check for next_code == */
  195.         /* lzw_decode_max every time: just checking at power */
  196.         /* of 2 boundaries stops us one code too soon. */
  197.         if ( next_code == lzw_decode_max - 1 )
  198.         {    s->end_status = ERRC;
  199.             goto out;
  200.         }
  201.         dc_next->datum = *p1;    /* first char of string */
  202.         ++prev_len;
  203.         dc_next->len = min(prev_len, 255);
  204.         dc_next->prefix = prev_code;
  205.         dc_next++;
  206.         if_debug4('W', "[W]decoding 0x%x=0x%x+%c(%d)\n",
  207.               next_code, prev_code, *p1, min(len, 255));
  208.         if ( ++next_code == code_mask )
  209.         {    /* Crossed a power of 2. */
  210.             /* We have to make a strange special check for */
  211.             /* reaching the end of the code space. */
  212.             if ( next_code != lzw_decode_max - 1 )
  213.             {    code_size = ++(s->state.lzw.code_size);
  214.                 code_mask = (1 << code_size) - 1;
  215.                 if_debug2('w', "[w]crossed power of 2: new code_size=%d, next_code=%d\n",
  216.                       code_size, next_code);
  217.             }
  218.         }
  219.     }
  220.     prev_code = code;
  221.     prev_len = len;
  222.     goto top;
  223. out:    s->cptr = s->cbuf - 1;
  224.     s->endptr = p - 1;
  225.     s->state.lzw.prev_code = prev_code;
  226.     s->bits = bits;
  227.     s->bits_left = bits_left;
  228.     s->state.lzw.next_code = next_code;
  229.     if_debug3('w', "[w]decoded %d bytes, prev_code=%d, next_code=%d\n",
  230.           (int)(s->endptr - s->cptr), prev_code, next_code);
  231.     return 0;
  232. }
  233.  
  234. /* Stream procedures */
  235. const stream_procs s_LZWD_procs =
  236.    {    s_std_noavailable, NULL, s_std_read_flush, s_std_close,
  237.     s_LZWD_read_buf, NULL
  238.    };
  239.